package cn.edu.zzuli.linkedlist;

//约瑟夫环问题
public class josepfu {

    public static void main(String[] args) {

        CircleLinkedList list = new CircleLinkedList();
        list.add(5);
        // list.list();

        list.popNums(1, 2, 5);
        
    }

}

//环形链表
class CircleLinkedList {
    //第一个小孩节点
    private Boy first = null;

    //添加小孩，构成环形链表
    public void add(int nums) {
        //如果nums < 1 不允许，至少要有一个
        if (nums < 1) {
            System.out.println("nums 值不正确");
            return;
        }

        //辅助节点
        Boy curBoy = null;

        //使用循环来创建环形链表
        for (int i = 1; i <= nums; i++) {
            //根据编号，创建小孩节点
            Boy boy = new Boy(i);
            //如果是第一个小孩
            //这比较特殊，它可以与自己构成环
            if (i == 1) {
                first = boy;
                first.setNext(first);
                //curBoy指向第一个小孩
                curBoy = first;
            } else {
                //curBoy 指向新节点
                curBoy.setNext(boy);
                boy.setNext(first);
                //curBoy 后移一下
                curBoy = boy;
            }
        }
    }

    //遍历当前的环形链表
    public void list() {
        if (first == null) {
            System.out.println("链表为空");
            return;
        }

        Boy curBoy = first;

        while(true) {
            System.out.println(curBoy);
            if( curBoy.getNext() == first) {
                break;
            }

            //curBoy 后移
            curBoy = curBoy.getNext();
        }
    }

    //获取出队顺序
    public void popNums(int startNo, int count, int nums) {
        if (first == null || startNo < 1 || startNo > nums || nums < 1) {
            System.out.println("参数有误");
            return;
        }

        //指向最后一个节点
        Boy helper = first;

        if (startNo == 1) {
            while(true) {
                if( helper.getNext() == first) {
                    break;
                }
    
                //curBoy 后移
                helper = helper.getNext();
            }
        }

        
        //移动开始报数的那个小孩的位置
        for(int i = 0; i < startNo -1; i++) {
            helper = first;
            first = first.getNext();
        }

        while(true) {
            //说明圈中只有一个节点
            if(helper == first) {
                break;
            }

            for(int i = 0; i < count - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }

            System.out.println(first+": 出圈");

            //出圈后，删除这个节点
            first = first.getNext();
            helper.setNext(first);
        }

        System.out.println(first+": 最后出圈");
    }
}

class Boy {
    private int no;
    
    private Boy next;

    public Boy(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "Boy [no=" + no + "]";
    }

    
}